package com.leetcode.algorithm.y19.m01;

import com.leetcode.algorithm.common.TreeNode;

/**
 * leetcode-cn.com
 * 
 * (TODO)437. 路径总和 III
 * (TODO)733. 图像渲染
 * (done)463. 岛屿的周长
 * (TODO)695. 岛屿的最大面积
 * (TODO)200. 岛屿的个数
 * (TODO)669. 修剪二叉搜索树
 * (TODO)687. 最长同值路径
 * (TODO)893. 特殊等价字符串组
 * (TODO)812. 最大三角形面积
 * 
 * @author: jie.deng
 * @time: 2019年1月17日 下午2:31:26
 */
public class MySolutionToDo {
	
	/**
     * 437. 路径总和 III
     * 
     * 给定一个二叉树，它的每个结点都存放着一个整数值。
     * 
     * 找出路径和等于给定数值的路径总数。
     * 
     * 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
     * 
     * 二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
     * 
     * 示例：
     * 
     * root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
     * 
     *       10
     *      /  \
     *     5   -3
     *    / \    \
     *   3   2   11
     *  / \   \
     * 3  -2   1
     * 
     * 返回 3。和等于 8 的路径有:
     * 
     * 1.  5 -> 3
     * 2.  5 -> 2 -> 1
     * 3.  -3 -> 11
     * @param root
     * @param sum
     * @return
     */
    public int pathSum(TreeNode root, int sum) {
		return sum;
    }
    
    /**
     * 669. 修剪二叉搜索树
     * 
     * 给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。
     * 
     * 示例 1:
     * 
     * 输入: 
     *     1
     *    / \
     *   0   2
     * 
     *   L = 1
     *   R = 2
     * 
     * 输出: 
     *     1
     *       \
     *        2
     * 示例 2:
     * 
     * 输入: 
     *     3
     *    / \
     *   0   4
     *    \
     *     2
     *    /
     *   1
     * 
     *   L = 1
     *   R = 3
     * 
     * 输出: 
     *       3
     *      / 
     *    2   
     *   /
     *  1
     * @param root
     * @param L
     * @param R
     * @return
     */
    public TreeNode trimBST(TreeNode root, int L, int R) {
		return root;
    }
    
	/**
     * 687. 最长同值路径
     * 
     * 给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
     * 
     * 注意：两个节点之间的路径长度由它们之间的边数表示。
     * 
     * 示例 1:
     * 
     * 输入:
     * 
     *               5
     *              / \
     *             4   5
     *            / \   \
     *           1   1   5
     * 输出:
     * 
     * 2
     * 示例 2:
     * 
     * 输入:
     * 
     *               1
     *              / \
     *             4   5
     *            / \   \
     *           4   4   5
     * 输出:
     * 
     * 2
     * 注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。
     * @param root
     * @return
     */
	public int longestUnivaluePath(TreeNode root) {
		if (root == null) {
			return 0;
		}
		return Math.max(longestUnivaluePath(root.left, root.val, 0, 0), longestUnivaluePath(root.right, root.val, 0, 0));
	}
	/**
	 * 
	 * @param node 当前节点
	 * @param val 重复元素
	 * @param cnt 重复元素出现的次数
	 * @param maxCnt
	 * @return
	 */
	private int longestUnivaluePath(TreeNode node, Integer val, int cnt, int maxCnt) {
		if (node == null) {
			return Math.max(cnt, maxCnt);
		}
		if (node.val == val) {
			return Math.max(longestUnivaluePath(node.left, val, cnt + 1, maxCnt),
					longestUnivaluePath(node.right, val, cnt + 1, maxCnt));
		}
		return Math.max(longestUnivaluePath(node.left, node.val, 0, Math.max(cnt, maxCnt)), longestUnivaluePath(node.right, node.val, 0, Math.max(cnt, maxCnt)));
	}
	
	/**
	 * 733. 图像渲染
	 * 
      * 有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。
      * 
      * 给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。
      * 
      * 为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。
      * 
      * 最后返回经过上色渲染后的图像。
      * 
      * 示例 1:
      * 
      * 输入: 
      * image = [[1,1,1],[1,1,0],[1,0,1]]
      * sr = 1, sc = 1, newColor = 2
      * 输出: [[2,2,2],[2,2,0],[2,0,1]]
      * 解析: 
      * 在图像的正中间，(坐标(sr,sc)=(1,1)),
      * 在路径上所有符合条件的像素点的颜色都被更改成2。
      * 注意，右下角的像素没有更改为2，
      * 因为它不是在上下左右四个方向上与初始点相连的像素点。
      * 注意:
      * 
      * image 和 image[0] 的长度在范围 [1, 50] 内。
      * 给出的初始点将满足 0 <= sr < image.length 和 0 <= sc < image[0].length。
      * image[i][j] 和 newColor 表示的颜色值在范围 [0, 65535]内。
	 * @param image
	 * @param sr
	 * @param sc
	 * @param newColor
	 * @return
	 */
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
		return image;
    }
    
    /**
     * 463. 岛屿的周长
     * 
     * 给定一个包含 0 和 1 的二维网格地图，其中 1 表示陆地 0 表示水域。
     * 
     * 网格中的格子水平和垂直方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
     * 
     * 岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。
     * 
     *  
     * 
     * 示例 :
     * 
     * 输入:
     * [[0,1,0,0],
     *  [1,1,1,0],
     *  [0,1,0,0],
     *  [1,1,0,0]]
     * 
     * 输出: 16
     * 
     * 解释: 它的周长是下面图片中的 16 个黄色的边：
     * @param grid
     * @return
     */
    public int islandPerimeter(int[][] grid) {
		if (grid == null) {
			return 0;
		}
		int row = grid.length;
		if (row == 0) {
			return 0;
		}
		int col = grid[0].length;
		int sum = 0;
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				if (grid[i][j] == 1) {
					// 左边为0或者没有格子，周长加1
					if (j == 0 || grid[i][j - 1] == 0) {
						sum++;
					}
					// 右边为0或者没有格子，周长加1
					if (j == col - 1 || grid[i][j + 1] == 0) {
						sum++;
					}
					// 上边为0或者没有格子，周长加1
					if (i == 0 || grid[i - 1][j] == 0) {
						sum++;
					}
					// 下边为0或者没有格子，周长加1
					if (i == row - 1 || grid[i + 1][j] == 0) {
						sum++;
					}
				}
			}
		}
		return sum;
	}
    
	/**
	 * 695. 岛屿的最大面积
     * 给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。
     * 找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)
     * 
     * 示例 1:
     * [[0,0,1,0,0,0,0,1,0,0,0,0,0],
     *  [0,0,0,0,0,0,0,1,1,1,0,0,0],
     *  [0,1,1,0,1,0,0,0,0,0,0,0,0],
     *  [0,1,0,0,1,1,0,0,1,0,1,0,0],
     *  [0,1,0,0,1,1,0,0,1,1,1,0,0],
     *  [0,0,0,0,0,0,0,0,0,0,1,0,0],
     *  [0,0,0,0,0,0,0,1,1,1,0,0,0],
     *  [0,0,0,0,0,0,0,1,1,0,0,0,0]]
     * 对于上面这个给定矩阵应返回 6。注意答案不应该是11，因为岛屿只能包含水平或垂直的四个方向的‘1’。
     * 
     * 示例 2:
     * [[0,0,0,0,0,0,0,0]]
     * 对于上面这个给定的矩阵, 返回 0。
     * 
     * 注意: 给定的矩阵grid 的长度和宽度都不超过 50。
	 * @param grid
	 * @return
	 */
    public int maxAreaOfIsland(int[][] grid) {
		return 0;
    }
    
    /**
     * 200. 岛屿的个数
     * 
     * 给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
     * 
     * 示例 1:
     * 
     * 输入:
     * 11110
     * 11010
     * 11000
     * 00000
     * 
     * 输出: 1
     * 示例 2:
     * 
     * 输入:
     * 11000
     * 11000
     * 00100
     * 00011
     * 
     * 输出: 3
     * @param grid
     * @return
     */
    public int numIslands(char[][] grid) {
		return 0;
    }
    
	/**
     * 893. 特殊等价字符串组
     * 
     * 你将得到一个字符串数组 A。
     * 
     * 如果经过任意次数的移动，S == T，那么两个字符串 S 和 T 是特殊等价的。
     * 
     *  
     * 
     * 一次移动包括选择两个索引 i 和 j，且 i％2 == j％2，并且交换 S[j] 和 S [i]。
     * 
     * 现在规定，A 中的特殊等价字符串组是 A 的非空子集 S，这样不在 S 中的任何字符串与 S 中的任何字符串都不是特殊等价的。
     * 
     *  
     * 
     * 返回 A 中特殊等价字符串组的数量。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：["a","b","c","a","c","c"]
     * 输出：3
     * 解释：3 组 ["a","a"]，["b"]，["c","c","c"]
     * 示例 2：
     * 
     * 输入：["aa","bb","ab","ba"]
     * 输出：4
     * 解释：4 组 ["aa"]，["bb"]，["ab"]，["ba"]
     * 示例 3：
     * 
     * 输入：["abc","acb","bac","bca","cab","cba"]
     * 输出：3
     * 解释：3 组 ["abc","cba"]，["acb","bca"]，["bac","cab"]
     * 示例 4：
     * 
     * 输入：["abcd","cdab","adcb","cbad"]
     * 输出：1
     * 解释：1 组 ["abcd","cdab","adcb","cbad"]
     *  
     * 
     * 提示：
     * 
     * 1 <= A.length <= 1000
     * 1 <= A[i].length <= 20
     * 所有 A[i] 都具有相同的长度。
     * 所有 A[i] 都只由小写字母组成。
     * @param A
     * @return
     */
    public int numSpecialEquivGroups(String[] A) {
		return 0;
    }
    
    /**
     * 812. 最大三角形面积
     * 给定包含多个点的集合，从其中取三个点组成三角形，返回能组成的最大三角形的面积。
     * 
     * 示例:
     * 输入: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
     * 输出: 2
     * 解释: 
     * 这五个点如下图所示。组成的橙色三角形是最大的，面积为2。
     * 
     * 
     * 注意:
     * 
     * 3 <= points.length <= 50.
     * 不存在重复的点。
     *  -50 <= points[i][j] <= 50.
     * 结果误差值在 10^-6 以内都认为是正确答案。
     * @param points
     * @return
     */
    public double largestTriangleArea(int[][] points) {
		return 0;
    }    
}
